package interview.Algorithms;

import java.util.ArrayList;
import java.util.Iterator;

public class MST {
	public Iterable<Edge> primsMethod(Graph graph){
		ArrayList<Edge> mstEdge = new ArrayList<Edge>();
		boolean[] vertexAdded =new boolean[graph.getVertices()];
		boolean[] vertexMST =  new boolean[graph.getVertices()];
		int vertexSeen = 1;
		vertexAdded[1]= true;
		Iterator<Edge> edges = null; 
		MinPriorityQueue<Edge> pq = new MinPriorityQueue<>(graph.getEdges());
		Edge edgeAdded = null;
		int currentVertex = 1;
		while (vertexSeen < graph.getVertices()-1){
			edges = (graph.getVertexInfo(currentVertex).getEdges());     
			while(edges.hasNext()){
				Edge tempEdge = (Edge)edges.next();
				if (!(vertexMST[tempEdge.getU()] && vertexMST[tempEdge.getV()]) && !tempEdge.isVisited()){
					tempEdge.setVisited(true);
					pq.insert(tempEdge);
				}
			}
			
			edgeAdded = (Edge)pq.deleteMin();
			while (vertexMST[edgeAdded.getU()] && vertexMST[edgeAdded.getV()])
					edgeAdded = (Edge)pq.deleteMin();
			
			mstEdge.add(edgeAdded);			
			vertexAdded[currentVertex]=true;

			vertexSeen++;
			System.out.println("Edges added: "+edgeAdded);
			if(vertexAdded[edgeAdded.getU()]) 
				currentVertex = edgeAdded.getV();			
			else
				currentVertex=edgeAdded.getU();
			
			vertexMST[edgeAdded.getU()]=true;
			vertexMST[edgeAdded.getV()]=true;
			
		}
		return mstEdge;		
	}
}
